home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqbuild / csg4.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  10.5 KB  |  463 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. /*
  5.  * 
  6.  * NOTES
  7.  * -----
  8.  * Brushes that touch still need to be split at the cut point to make a tjunction
  9.  * 
  10.  */
  11.  
  12. struct visfacet **validfaces;
  13.  
  14. struct visfacet *inside, *outside;        // 8
  15. int brushfaces;                    // 4
  16. int csgfaces;                    // 4
  17. int csgmergefaces;                // 4
  18.  
  19. void DrawList(register struct visfacet * list)
  20. {
  21.   for (; list; list = list->next)
  22.     Draw_DrawFace(list);
  23. }
  24.  
  25. /*
  26.  * ==================
  27.  * NewFaceFromFace
  28.  * 
  29.  * Duplicates the non point information of a face, used by SplitFace and
  30.  * MergeFace.
  31.  * ==================
  32.  */
  33. struct visfacet *NewFaceFromFace(register struct visfacet * in, register int points)
  34. {
  35.   struct visfacet *newf;
  36.  
  37.   newf = AllocFace(points);
  38.  
  39.   newf->planenum = in->planenum;
  40.   newf->texturenum = in->texturenum;
  41.   newf->planeside = in->planeside;
  42.   newf->original = in->original;
  43.   newf->contents[0] = in->contents[0];
  44.   newf->contents[1] = in->contents[1];
  45.  
  46.   return newf;
  47. }
  48.  
  49. /*
  50.  * ==================
  51.  * SplitFace
  52.  * 
  53.  * ==================
  54.  */
  55. void SplitFace(struct visfacet * in, struct plane * split, struct visfacet ** front, struct visfacet ** back)
  56. {
  57.   //vec_t dists[MAXEDGES + 1];
  58.   //int sides[MAXEDGES + 1];
  59.   vec_t *dists = (vec_t *)tmalloc(MAXEDGES * sizeof(vec_t));
  60.   int *sides = (int *)tmalloc(MAXEDGES * sizeof(int));
  61.   int counts[3];
  62.   vec_t dot;
  63.   int i, j;
  64.   struct visfacet *newf, *new2;
  65.   vec_t *p1, *p2;
  66.   vec3_t mid;
  67.  
  68.   if (in->numpoints < 0)
  69.     Error("SplitFace: freed face");
  70.   counts[0] = counts[1] = counts[2] = 0;
  71.  
  72. // determine sides for each point
  73.   for (i = 0; i < in->numpoints; i++) {
  74.     dot = DotProduct(in->pts[i], split->normal);
  75.     dot -= split->dist;
  76.     dists[i] = dot;
  77.     if (dot > ON_EPSILON)
  78.       sides[i] = SIDE_FRONT;
  79.     else if (dot < -ON_EPSILON)
  80.       sides[i] = SIDE_BACK;
  81.     else
  82.       sides[i] = SIDE_ON;
  83.     counts[sides[i]]++;
  84.   }
  85.   sides[i] = sides[0];
  86.   dists[i] = dists[0];
  87.  
  88.   if (!counts[0]) {
  89.     *front = NULL;
  90.     *back = in;
  91.     tfree(dists);
  92.     tfree(sides);
  93.     return;
  94.   }
  95.   if (!counts[1]) {
  96.     *front = in;
  97.     *back = NULL;
  98.     tfree(dists);
  99.     tfree(sides);
  100.     return;
  101.   }
  102.  
  103.   *back = newf = NewFaceFromFace(in, MAXEDGES);
  104.   *front = new2 = NewFaceFromFace(in, MAXEDGES);
  105.  
  106. // distribute the points and generate splits
  107.  
  108.   for (i = 0; i < in->numpoints; i++) {
  109.     if (newf->numpoints > MAXEDGES || new2->numpoints > MAXEDGES)
  110.       Error("SplitFace: numpoints > MAXEDGES");
  111.  
  112.     p1 = in->pts[i];
  113.  
  114.     if (sides[i] == SIDE_ON) {
  115.       VectorCopy(p1, newf->pts[newf->numpoints]);
  116.       newf->numpoints++;
  117.       VectorCopy(p1, new2->pts[new2->numpoints]);
  118.       new2->numpoints++;
  119.       continue;
  120.     }
  121.  
  122.     if (sides[i] == SIDE_FRONT) {
  123.       VectorCopy(p1, new2->pts[new2->numpoints]);
  124.       new2->numpoints++;
  125.     }
  126.     else {
  127.       VectorCopy(p1, newf->pts[newf->numpoints]);
  128.       newf->numpoints++;
  129.     }
  130.  
  131.     if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  132.       continue;
  133.  
  134.     // generate a split point
  135.     p2 = in->pts[(i + 1) % in->numpoints];
  136.  
  137.     dot = dists[i] / (dists[i] - dists[i + 1]);
  138.     for (j = 0; j < 3; j++) {                               // avoid round off error when possible
  139.  
  140.       if (split->normal[j] == 1)
  141.     mid[j] = split->dist;
  142.       else if (split->normal[j] == -1)
  143.     mid[j] = -split->dist;
  144.       else
  145.     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  146.     }
  147.  
  148.     VectorCopy(mid, newf->pts[newf->numpoints]);
  149.     newf->numpoints++;
  150.     VectorCopy(mid, new2->pts[new2->numpoints]);
  151.     new2->numpoints++;
  152.   }
  153.  
  154.   if (newf->numpoints > MAXEDGES || new2->numpoints > MAXEDGES)
  155.     Error("SplitFace: numpoints > MAXEDGES");
  156.  
  157.   RecalcFace(newf);
  158.   RecalcFace(new2);
  159.   //if ((newf->numpoints > in->numpoints) || (new2->numpoints > in->numpoints))
  160.   //  mprintf("SplitFace: heavy split (%d to %d + %d)\n", in->numpoints, newf->numpoints, new2->numpoints);
  161.  
  162. #if 0
  163.   CheckFace(newf);
  164.   CheckFace(new2);
  165. #endif
  166.  
  167. // free the original face now that is is represented by the fragments
  168.   FreeFace(in);
  169.   tfree(dists);
  170.   tfree(sides);
  171. }
  172.  
  173. /*
  174.  * =================
  175.  * ClipInside
  176.  * 
  177.  * Clips all of the faces in the inside list, possibly moving them to the
  178.  * outside list or spliting it into a piece in each list.
  179.  * 
  180.  * Faces exactly on the plane will stay inside unless overdrawn by later brush
  181.  * 
  182.  * frontside is the side of the plane that holds the outside list
  183.  * =================
  184.  */
  185. void ClipInside(__memBase, register int splitplane, register int frontside, register bool precedence)
  186. {
  187.   struct visfacet *f, *next;
  188.   struct visfacet *frags[2];
  189.   struct visfacet *insidelist;
  190.   struct plane *split;
  191.  
  192. #ifdef EXHAUSIVE_CHECK
  193.   if(splitplane >= bspMem->numbrushplanes || splitplane < 0)
  194.     Error("looking for nonexisting plane %d\n", splitplane);
  195. #endif
  196.   split = &bspMem->brushplanes[splitplane];
  197.  
  198.   insidelist = NULL;
  199.   for (f = inside; f; f = next) {
  200.     next = f->next;
  201.  
  202.     if (f->planenum == splitplane) {                           // exactly on, handle special
  203.  
  204.       if (frontside != f->planeside || precedence) {                   // allways clip off opposite faceing
  205.  
  206.     frags[frontside] = NULL;
  207.     frags[!frontside] = f;
  208.       }
  209.       else {                                       // leave it on the outside
  210.  
  211.     frags[frontside] = f;
  212.     frags[!frontside] = NULL;
  213.       }
  214.     }
  215.     else {                                       // proper split
  216.  
  217.       SplitFace(f, split, &frags[0], &frags[1]);
  218.     }
  219.  
  220.     if (frags[frontside]) {
  221.       frags[frontside]->next = outside;
  222.       outside = frags[frontside];
  223.     }
  224.     if (frags[!frontside]) {
  225.       frags[!frontside]->next = insidelist;
  226.       insidelist = frags[!frontside];
  227.     }
  228.   }
  229.  
  230.   inside = insidelist;
  231. }
  232.  
  233. /*
  234.  * ==================
  235.  * SaveOutside
  236.  * 
  237.  * Saves all of the faces in the outside list to the bsp plane list
  238.  * ==================
  239.  */
  240. void SaveOutside(__memBase, register bool mirror)
  241. {
  242.   struct visfacet *f, *next, *newf;
  243.   int i;
  244.   int planenum;
  245.  
  246.   for (f = outside; f; f = next) {
  247.     next = f->next;
  248.     csgfaces++;
  249.     Draw_DrawFace(f);
  250.     planenum = f->planenum;
  251.  
  252.     if (mirror) {
  253.       newf = NewFaceFromFace(f, f->numpoints);
  254.  
  255.       newf->numpoints = f->numpoints;
  256.       newf->planeside = f->planeside ^ 1;                       // reverse side
  257.  
  258.       newf->contents[0] = f->contents[1];
  259.       newf->contents[1] = f->contents[0];
  260.  
  261.       for (i = 0; i < f->numpoints; i++)                       // add points backwards
  262.        {
  263.     VectorCopy(f->pts[f->numpoints - 1 - i], newf->pts[i]);
  264.       }
  265.     }
  266.     else
  267.       newf = NULL;
  268.  
  269.     validfaces[planenum] = MergeFaceToList(bspMem, f, validfaces[planenum]);
  270.     if (newf)
  271.       validfaces[planenum] = MergeFaceToList(bspMem, newf, validfaces[planenum]);
  272.  
  273.     validfaces[planenum] = FreeMergeListScraps(validfaces[planenum]);
  274.   }
  275. }
  276.  
  277. /*
  278.  * ==================
  279.  * FreeInside
  280.  * 
  281.  * Free all the faces that got clipped out
  282.  * ==================
  283.  */
  284. void FreeInside(register int contents)
  285. {
  286.   struct visfacet *f, *next;
  287.  
  288.   for (f = inside; f; f = next) {
  289.     next = f->next;
  290.  
  291.     if (contents != CONTENTS_SOLID) {
  292.       f->contents[0] = contents;
  293.       f->next = outside;
  294.       outside = f;
  295.     }
  296.     else
  297.       FreeFace(f);
  298.   }
  299. }
  300.  
  301. //==========================================================================
  302.  
  303. /*
  304.  * ==================
  305.  * BuildSurfaces
  306.  * 
  307.  * Returns a chain of all the external surfaces with one or more visible
  308.  * faces.
  309.  * ==================
  310.  */
  311. struct surface *BuildSurfaces(__memBase)
  312. {
  313.   struct visfacet **f;
  314.   struct visfacet *count;
  315.   int i;
  316.   struct surface *s;
  317.   struct surface *surfhead;
  318.  
  319.   surfhead = NULL;
  320.  
  321.   f = validfaces;
  322.   for (i = 0; i < bspMem->numbrushplanes; i++, f++) {
  323.     if (*f) {                                       // !nothing left on this plane
  324.       // create a new surface to hold the faces on this plane
  325.       s = AllocSurface();
  326.       s->planenum = i;
  327.       s->next = surfhead;
  328.       surfhead = s;
  329.       s->faces = *f;
  330.       for (count = s->faces; count; count = count->next)
  331.         csgmergefaces++;
  332.       CalcSurfaceInfo(s);                               // bounding box and flags
  333.     }
  334.     /** mprogress(bspMem->numbrushplanes, i + 1); **/
  335.   }
  336.  
  337.   return surfhead;
  338. }
  339.  
  340. //==========================================================================
  341.  
  342. /*
  343.  * ==================
  344.  * CopyFacesToOutside
  345.  * ==================
  346.  */
  347. void CopyFacesToOutside(register struct brush * b)
  348. {
  349.   struct visfacet *f, *newf;
  350.  
  351.   outside = NULL;
  352.  
  353.   for (f = b->faces; f; f = f->next) {
  354.     brushfaces++;
  355. #if 0
  356.     {
  357.       int i;
  358.  
  359.       for (i = 0; i < f->numpoints; i++)
  360.     mprintf("(%f,%f,%f) ", f->pts[i][0], f->pts[i][1], f->pts[i][2]);
  361.       mprintf("\n");
  362.     }
  363. #endif
  364.     newf = AllocFace(f->numpoints);
  365.     CopyFace(newf, f);
  366.     newf->next = outside;
  367.     newf->contents[0] = CONTENTS_EMPTY;
  368.     newf->contents[1] = b->contents;
  369.     outside = newf;
  370.   }
  371. }
  372.  
  373. /*
  374.  * ==================
  375.  * CSGFaces
  376.  * 
  377.  * Returns a list of surfaces containing aall of the faces
  378.  * ==================
  379.  */
  380. struct surface *CSGFaces(__memBase, struct brushset * bs)
  381. {
  382.   struct brush *b1, *b2;
  383.   int i, j;
  384.   bool overwrite;
  385.   struct visfacet *f;
  386.   struct surface *surfhead;
  387.  
  388.   mprintf("----- CSGFaces ----------\n");
  389.  
  390.   /* added by niels */
  391.   if(!(validfaces = (struct visfacet **)tmalloc(sizeof(struct visfacet *) * bspMem->numbrushplanes)))
  392.     Error("CSGFaces: failed to allocate validfaces!\n");
  393.  
  394.   csgfaces = brushfaces = csgmergefaces = 0;
  395.  
  396.   Draw_ClearWindow();
  397.  
  398. //
  399.   // do the solid faces
  400.   //
  401.   for (b1 = bs->brushes, j = 0; b1; b1 = b1->next) {
  402.     mprogress(bs->numbrushes, ++j);
  403.   
  404.     // set outside to a copy of the brush's faces
  405.     CopyFacesToOutside(b1);
  406.  
  407.     overwrite = FALSE;
  408.  
  409.     for (b2 = bs->brushes; b2; b2 = b2->next) {
  410.       // see if b2 needs to clip a chunk out of b1
  411.  
  412.       if (b1 == b2) {
  413.     overwrite = TRUE;                               // later brushes now overwrite
  414.  
  415.     continue;
  416.       }
  417.  
  418.       // check bounding box first
  419.       for (i = 0; i < 3; i++)
  420.     if (b1->mins[i] > b2->maxs[i] || b1->maxs[i] < b2->mins[i])
  421.       break;
  422.       if (i < 3)
  423.     continue;
  424.  
  425.       // divide faces by the planes of the new brush
  426.  
  427.       inside = outside;
  428.       outside = NULL;
  429.  
  430.       for (f = b2->faces; f; f = f->next)
  431.     ClipInside(bspMem, f->planenum, f->planeside, overwrite);
  432.  
  433.       // these faces are continued in another brush, so get rid of them
  434.       if (b1->contents == CONTENTS_SOLID && b2->contents <= CONTENTS_WATER)
  435.     FreeInside(b2->contents);
  436.       else
  437.     FreeInside(CONTENTS_SOLID);
  438.     }
  439.  
  440.     // all of the faces left in outside are real surface faces
  441.     if (b1->contents != CONTENTS_SOLID)
  442.       SaveOutside(bspMem, TRUE);                           // mirror faces for inside view
  443.  
  444.     else
  445.       SaveOutside(bspMem, FALSE);
  446.   }
  447.  
  448. #if 0
  449.   if (!csgfaces)
  450.     Error("No faces");
  451. #endif
  452.  
  453.   surfhead = BuildSurfaces(bspMem);
  454.  
  455.   mprintf("%5i brushfaces\n", brushfaces);
  456.   mprintf("%5i csgfaces\n", csgfaces);
  457.   mprintf("%5i mergedfaces\n", csgmergefaces);
  458.  
  459.   /* added by niels */
  460.   tfree(validfaces);
  461.   return surfhead;
  462. }
  463.